package leetcode2;

import java.util.Scanner;

public class LeetCodeMain136 {
    //快速排序
    public static int[] arr=null;
    public static void main(String[] args) {
        Scanner in=new Scanner(System.in);
        System.out.println("请输入数组的数据");
        int n=in.nextInt();
        arr=new int[n];
        for (int i = 0; i < n; i++) {
            arr[i]=in.nextInt();
        }
        quick_sort(arr,0,n-1);
        for (int num:arr) {
            System.out.println(num);
        }
    }

    private static void quick_sort(int[] arr, int l, int r) {
        if (l>=r) {
            return;
        }
        int x=arr[l];
        int i=l-1;
        int j=r+1;
        while (i<j){
            while (arr[++i]<x);
            while (arr[--j]>x);
            if (i<j){
                int tmp=arr[i];
                arr[i]=arr[j];
                arr[j]=tmp;
            }
        }
        quick_sort(arr, l, j);
        quick_sort(arr, j+1, r);
    }
}
